class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        // 由于我下面那种写法是先遍历amount，再遍历coins，所以内层循环会提前退出，所以需要对coins先进行排序，保证从小到大一个一个去判断
        sort(coins.begin(), coins.end());

        // 给dp数组每个位置赋初值为INT_MAX是为了最后判断是否能填满amount,要用long long 类型
        vector<long long> dp(amount + 1, INT_MAX);
        dp[0] = 0;

        for(int i = 1; i <= amount; i++)
        {
            // dp[i] = INT_MAX;     // 在这里初始化也可以
            for(int j = 0; j < coins.size() && coins[j] <= i; j++)
                dp[i] = min(dp[i], dp[i - coins[j]] + 1);

            // 排查错误的方法：打印dp数组
            // cout << i << ":" << dp[i] << endl;   
        }

        // 如果是下面这种遍历顺序就不用对coins数组排序，因为每种面额都会被判断到
        // for(int i = 0; i < coins.size(); i++)
        // {
        //     for(int j = coins[i]; j <= amount; j++)
        //         dp[j] = min(dp[j], dp[j - coins[i]] + 1);
        // }
        // return dp[amount] == INT_MAX ? -1 : dp[amount];
    }
};